Search for: All records

Abstract Distinguishing between continuous and first-order phase transitions is a major challenge in random discrete systems. We study the topic for events with recursive structure on Galton–Watson trees. For example, let $$\mathcal{T}_1$$ be the event that a Galton–Watson tree is infinite and let $$\mathcal{T}_2$$ be the event that it contains an infinite binary tree starting from its root. These events satisfy similar recursive properties: $$\mathcal{T}_1$$ holds if and only if $$\mathcal{T}_1$$ holds for at least one of the trees initiated by children of the root, and $$\mathcal{T}_2$$ holds if and only if $$\mathcal{T}_2$$ holds for at least two of these trees. The probability of $$\mathcal{T}_1$$ has a continuous phase transition, increasing from 0 when the mean of the child distribution increases above 1. On the other hand, the probability of $$\mathcal{T}_2$$ has a first-order phase transition, jumping discontinuously to a non-zero value at criticality. Given the recursive property satisfied by the event, we describe the critical child distributions where a continuous phase transition takes place. In many cases, we also characterise the event undergoing the phase transition. 

The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $$\unicode[STIX]{x1D707}$$ on the full $$d$$ -ary tree of height $$n$$ . If $$\unicode[STIX]{x1D707}=\unicode[STIX]{x1D6FA}(d^{2})$$ , all of the vertices are visited in time $$\unicode[STIX]{x1D6E9}(n\log n)$$ with high probability. Conversely, if $$\unicode[STIX]{x1D707}=O(d)$$ the cover time is $$\exp (\unicode[STIX]{x1D6E9}(\sqrt{n}))$$ with high probability.